set associative cache

A compromise between a {direct mapped cache} and a {fully

associative cache} where each address is mapped to a certain

set of cache locations. The address space is divided into

blocks of m bytes (the {cache line} size), discarding the

bottom m address bits. An "n-way set associative" cache with

S sets has n cache locations in each set. Block b is mapped

to set "b mod S" and may be stored in any of the n locations

in that set with its upper address bits as a tag. To

determine whether block b is in the cache, set "b mod S" is

searched associatively for the tag.

A direct mapped cache could be described as "one-way set

associative", i.e. one location in each set whereas a fully

associative cache is N-way associative (where N is the total

number of blocks in the cache). Performance studies have

shown that is is generally more effective to increase number

of entries rather than associativity and that 2- to 16-way set

associative caches perform almost as well as fully associative

caches at little extra cost over direct mapping.